package ch09_05;

import java.util.*;

public class Solution {
    public static void printAllPermutations(String s) {
	char[] arr = s.toCharArray();
	Arrays.sort(arr);
	int[] count = {0};
	genAllPermutations(arr, 0, count);
    }

    private static void genAllPermutations(char[] arr, int index, int count[]) {
	if (index == arr.length) {
		count[0]++;
		System.out.print(count[0] + ":\t");
	    System.out.println(arr);
	    return;
	}
	Set<Character> memo = new HashSet<Character>();
	for (int i = index; i < arr.length; i++) {
	    if (memo.contains(arr[i])) {
		continue;
	    }
	    memo.add(arr[i]);
	    char tmp = arr[i];
	    arr[i] = arr[index];
	    arr[index] = tmp;
	    genAllPermutations(arr, index + 1, count);
	    tmp = arr[i];
	    arr[i] = arr[index];
	    arr[index] = tmp;
	}
    }

    public static void main(String[] args) {
	String s = "adbc";
	printAllPermutations(s);
    }
}